#include "dlinknode.h"

void dataStruct::CreateListF(DLinkNode*& L, ElementType a[], int n)
{
	L = new DLinkNode;
	L->next = nullptr;
	L->prior = nullptr;
	for (int i = 0; i < n; i++)
	{
		DLinkNode* node = new DLinkNode;
		node->data = a[i];
		node->next = L->next;
		node->prior = L;
		if (L->next != nullptr)
		{
			L->next->prior = node;
		}

		L->next = node;

	}
}

void dataStruct::CreateListR(DLinkNode*& L, ElementType a[], int n)
{
	DLinkNode* s, * r;
	L = new DLinkNode;
	r = L;
	for (int i = 0; i < n; i++)
	{
		s = new DLinkNode;
		s->data = a[i];
		r->next = s;
		s->prior = r;
		r = s;
	}

	r->next = nullptr;
}

void dataStruct::DispList(DLinkNode*& L)
{
	DLinkNode* p = L->next;
	cout << "DispList" << endl;
	while (p != nullptr)
	{
		cout << p->data << endl;
		p = p->next;
	}

	cout << "end" << endl;
}

void dataStruct::DestoryList(DLinkNode*& L)
{
	DLinkNode* p = L;
	while (p != nullptr)
	{
		DLinkNode* q = p->next;
		delete p;
		p = q;
	}
}

int dataStruct::ListLength(DLinkNode*& L)
{
	DLinkNode* p = L;
	int length = 0;
	while (p->next != nullptr)
	{
		length++;
		p = p->next;
	}
	return length;
}

bool dataStruct::ListEmpty(DLinkNode*& L)
{
	return !(L->next);
}

bool dataStruct::GetElem(DLinkNode* L, int i, ElementType& e)
{
	int j = 0;
	DLinkNode* p = L;
	while (p->next != nullptr)
	{
		p = p->next;
		j++;
		if (i == j)
		{
			e = p->data;
			return true;
		}
	}

	return false;
}

int dataStruct::LocateElem(DLinkNode* L, ElementType e)
{
	DLinkNode* p = L;
	int i = 0;
	while (p->next != nullptr)
	{
		p = p->next;
		i++;
		if (p->data == e)
		{
			return i;
		}
	}

	return 0;
}

bool dataStruct::ListInsert(DLinkNode*& L, int i, ElementType e)
{
	int j = 0;
	DLinkNode* p = L;
	if (i <= 0)
		return false;
	while (p->next != nullptr)
	{
		j++;	
		p = p->next;
		if (i == j + 1)
		{
			DLinkNode* node = new DLinkNode;
			node->data = e;
			node->next = p->next;
			node->prior = p;
			if (node->next != nullptr)
			{
				p->next->prior = node;
			}

			p->next = node;
			return true;
		}

	}
	return false;
}

bool dataStruct::ListDelete(DLinkNode*& L, int i, ElementType& e)
{
	int j = 0;
	DLinkNode* p = L;
	while (p->next != nullptr)
	{
		j++;
		p = p->next;
		if (i == j)
		{
			DLinkNode* pre = p->prior;
			pre->next = p->next;
			if (p->next != nullptr)
			{
				p->next->prior = pre;
			}
			
			delete p;
			return true;
		}
	}

	return false;
}

void dataStruct::reverse(DLinkNode*& L)
{
	DLinkNode* p = L->next;
	DLinkNode* n;
	L->next = nullptr;
	while (p != nullptr)
	{
		n = p->next;
		if (L->next != nullptr)
		{
			L->next->prior = p;
		}
		
		p->next = L->next;
		L->next = p;
		p->prior = L;
		p = n;
	}
}

void dataStruct::sort(DLinkNode*& L)
{
	DLinkNode* p = L->next->next;
	L->next->next = nullptr;
	DLinkNode* q;
	while (p != nullptr)
	{
		q = L->next;
		while (q != nullptr && p->data > q->data)
		{
			q = q->next;
		}

		if (q == nullptr)
			return;

		DLinkNode* n = p->next;
		p->next = q;
		if (q != nullptr)
		{
			p->prior = q->prior;
			q->prior = p;
		}
				
		p->prior->next = p;
		p = n;
	}
}

bool dataStruct::delelem(DLinkNode*& L, ElementType x)
{
	DLinkNode* p = L->next;
	while (p != L)
	{
		if (p->data == x)
		{
			p->prior->next = p->next;
			p->next->prior = p->prior;
			delete p;
			return true;
		}
	}
	return false;
}

bool dataStruct::Symm(DLinkNode* L)
{
	DLinkNode* p = L->next;
	DLinkNode* q = L->prior;
	while (1)
	{
		if (p == q || p == q->prior)
			return true;

		if (p->data == q->data)
		{
			p = p->next;
			q = q->next;
		}	
		else
		{
			return false;
		}
	}
}
